In recent years, increase in the size of cryptosystems has been an issue in public key cryptographic technologies for realizing secure communication without sharing keys in advance. In view of such background, a method for compressing the size of cryptosystems in public key cryptography has been proposed (see, for example, K. Rubin and A. Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, pp. 349-365, 2003). In this method, algebraic tori are used. Examples of methods for expressing an algebraic torus include an affine representation, a projective representation, and an extension field representation (see, for example, S. Galbraith, “Disguising Tori and Elliptic Curves”, IACR e-print Archive 2006/248, http://eprint.iacr.org/2006/248). In relation to an algebraic torus, decompression mapping refers to converting a member of the algebraic torus from an affine representation to a projective representation, from a projective representation to an extension field representation, or from an affine representation to an extension field representation. Compression mapping refers to converting a member of the algebraic torus from an extension field representation to a projective representation, from a projective representation to an affine representation or from an extension field representation to an affine representation. In algebraic torus-based public key cryptography, in steps of key generation, encryption and decryption, affine representations are used for input and output and extension field representations are used for arithmetic operation (see, for example, “Torus-Based Cryptography”). In view of calculation costs, it is known that the calculation cost for compression mapping and decompression mapping is low when projective representations are used for arithmetic operation (see, for example, T. Yonemura et al., “How to Construct the Cramer-Shoup Encryption Scheme on Algebraic Tori”, Proceedings of Computer Security Symposium, 2008). The arithmetic operation of the projective representations, however, has been basically performed similarly to that of the extension field representation (see, for example, T. Isogai et al., “Evaluation of Exponentiation on Algebraic Tori”, 2009 Symposium on Cryptography and Information Security, 2009).
Arithmetic operation of members of algebraic tori is required in public key cryptography, a key sharing scheme and a digital signature scheme realized by using algebraic tori. Specific examples of the arithmetic operation include multiplication, squaring, Frobenius mapping, inversion, and exponentiation. Calculation of exponentiation particularly takes much time. In the technology of “Evaluation of Exponentiation on Algebraic Tori”, calculation of exponentiation is performed by using projective representations and by combining multiplication, squaring and Frobenius mapping, which is disadvantageous in that the calculation cost of multiplication that constitutes a large part of the calculation cost of exponentiation is high.